//https://leetcode.cn/problems/n-queens/submissions/505032160/?envType=study-plan-v2&envId=top-100-liked
//暴力递归思路解决；
//https://www.yuque.com/huantaipingyang-jucwl/ipzeev/iw3ex5uascqkb7ga

#include <string>
#include <vector>
#include <set>

using namespace std;

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        if(n<1) return {};
        std::vector<int> record(n,0);
        process(0,record,n);
        return res;
    }
    void process(int i,std::vector<int>&record,int n){
        if(i==n) {
            std::vector<string> cur_vec;
            for(int i=0;i<record.size();++i){
                std::string tmp_str="";
                for(int j=0;j<n;++j){
                    char cur_char='.';
                    int cur_queue=record[i];
                    if(cur_queue==j){
                        cur_char='Q';
                    }
                    tmp_str+=cur_char;
                }
                cur_vec.emplace_back(tmp_str);
            }
            res.emplace_back(cur_vec);
            return;
        }
        for(int j=0;j<n;++j){
            if(isValid(record,i,j)){
                record[i]=j;
                process(i+1,record,n);
            }
        }
    }
    bool isValid(std::vector<int>& record,int i,int j){
        for(int k=0;k<i;++k){
            if(j==record[k]||std::abs(record[k]-j) == std::abs(i-k)){
                return false;
            }
        }
        return true;
    }
};